package g

/*
 * @lc app=leetcode.cn id=912 lang=golang
 *
 * [912] 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4
*/

// @lc code=start
func sortArray(nums []int) []int {
	// return sortArrayBubble(nums)  // Time Limit Exceeded
	// return sortArrayQuik(nums)
	// return sortArrayMerge(nums)
	return sortArrayHeap(nums)
}

// sortArrayBubble 冒泡,时间o(n^2),空间o(1)
func sortArrayBubble(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
	return nums
}

// sortArrayQuik 快排,时间o(nlogn),空间o(h)，h为递归层数，最小logn,最大n
func sortArrayQuik(nums []int) []int {
	quikSort(nums, 0, len(nums)-1)
	return nums
}
func quikSort(nums []int, l, r int) {
	if l < r {
		pivot := patition(nums, l, r)
		quikSort(nums, l, pivot-1)
		quikSort(nums, pivot+1, r)
	}
}
func patition(nums []int, l, r int) int {
	//随机取一个值，交换到最后 arr[r]，这里省去随机选取和交换
	//所有小于arr[r]的移到前边，大于arr[r]的移到后边
	//使用j来记录>arr[r]和<=arr[r]的分界线下标
	//j初始指向一个无效分割点l-1,l可能为0，j可能取-1(所以必须是有符号)
	j := l - 1
	for i := l; i <= r-1; i++ { //访问[l,r-1],包含l和r-1
		if nums[i] <= nums[r] {
			j++
			nums[i], nums[j] = nums[j], nums[i] //先移动分割点，然后再交换
		}
	}
	nums[j+1], nums[r] = nums[r], nums[j+1] //把最后基准元素和j+1位置交互
	return j + 1
}

// sortArrayMerge 归并排序,时间o(nlogn),空间o(n)
func sortArrayMerge(nums []int) []int {
	tmpNums := make([]int, len(nums))
	mergeSort(nums, 0, len(nums)-1, tmpNums)
	return nums
}

// mergeSort 归并排序利用了分治的思想来对序列进行排序。
// 对一个长为 n 的待排序的序列，我们将其分解成两个长度为 n/2 的子序列。
// 每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。
func mergeSort(nums []int, left, right int, tmpNums []int) {
	if left >= right {
		return
	}
	mid := (left + right) >> 1
	mergeSort(nums, left, mid, tmpNums)    // 保证左边有效性
	mergeSort(nums, mid+1, right, tmpNums) // 保证右边有序
	// 合并二个有序列表
	i := left
	j := mid + 1
	k := 0
	for i <= mid && j <= right {
		if nums[i] < nums[j] {
			tmpNums[k] = nums[i]
			i++
		} else {
			tmpNums[k] = nums[j]
			j++
		}
		k++
	}
	for i <= mid {
		tmpNums[k] = nums[i]
		k++
		i++
	}
	for j <= right {
		tmpNums[k] = nums[j]
		k++
		j++
	}
	// 将 tmp 数据拷贝回原来数组中
	for i := 0; i <= right-left; i++ {
		nums[i+left] = tmpNums[i]
	}
}

// sortArrayHeap 堆排序
// 思想就是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于它的子节点。
// 此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，
// 然后再调整堆顶元素使得剩下的 n−1 个元素仍为大根堆，
// 再重复执行以上操作我们即能得到一个有序的序列。
//
// 时间复杂度：O(nlog n)。初始化建堆的时间复杂度为 O(n)
// 建完堆以后需要进行 n−1 次调整，一次调整（即 maxHeapify） 的时间复杂度为 O(logn)
// 那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。
// 因此，总时间复杂度为 O(n+nlogn)=O(nlogn)。
// 空间复杂度：O(1)。只需要常数的空间存放若干变量。
func sortArrayHeap(arr []int) []int {
	rightIndex := len(arr) - 1 //这里必须是int，因为arr.size可能为0
	buildMaxHeap(arr, rightIndex)
	for i := rightIndex; i >= 1; i-- { //这里必须是int，因为len可能小于0
		arr[i], arr[0] = arr[0], arr[i] //最大值交换到后边已排序位置
		rightIndex--
		maxHeapify(arr, 0, rightIndex)
	}
	return arr
}

// buildMaxHeap 构建大顶推
func buildMaxHeap(arr []int, len int) {
	for i := len / 2; i >= 0; i-- { //这里必须是int，因为len可能小于0
		maxHeapify(arr, i, len)
	}
}

// maxHeapify 使第 i 个节点大于所有孩子节点
func maxHeapify(arr []int, i, len int) {
	for i*2+1 <= len {
		lChild := i*2 + 1
		rChild := i*2 + 2
		large := i
		if lChild <= len && arr[lChild] > arr[i] {
			large = lChild
		}
		if rChild <= len && arr[rChild] > arr[large] {
			large = rChild
		}
		if large != i {
			arr[i], arr[large] = arr[large], arr[i]
			i = large
		} else {
			break
		}
	}
}

// @lc code=end
